|
In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases. The name "Desargues graph" has also been used to refer to a ten-vertex graph, the complement of the Petersen graph, which can also be formed as the bipartite half of the 20-vertex Desargues graph.〔.〕 ==Constructions== There are several different ways of constructing the Desargues graph: *It is the generalized Petersen graph ''G''(10, 3). To form the Desargues graph in this way, connect ten of the vertices into a regular decagon, and connect the other ten vertices into a ten-pointed star that connects pairs of vertices at distance three in a second decagon. The Desargue graph consists of the 20 edges of these two polygons together with an additional 10 edges connecting points of one decagon to the corresponding points of the other. *It is the Levi graph of the Desargues configuration. This configuration consists of ten points and ten lines describing two perspective triangles, their center of perspectivity, and their axis of perspectivity. The Desargues graph has one vertex for each point, one vertex for each line, and one edge for every incident point-line pair. Desargues' theorem, named after 17th-century French mathematician Gérard Desargues, describes a set of points and lines forming this configuration, and the configuration and the graph take their name from it. *It is the bipartite double cover of the Petersen graph, formed by replacing each Petersen graph vertex by a pair of vertices and each Petersen graph edge by a pair of crossed edges. *It is the bipartite Kneser graph ''H''5,2. Its vertices can be labeled by the ten two-element subsets and the ten three-element subsets of a five-element set, with an edge connecting two vertices when one of the corresponding sets is a subset of the other. Equivalently, the Desargues graph is the induced subgraph of the 5-dimensional hypercube determined by the vertices of weight 2 and weight 3. *The Desargues graph is Hamiltonian and can be constructed from the LCF notation: ()5. As Erdos conjectured that for k positive, the subgraph of the 2k+1-dimensional hypercube induced by the vertices of weight k and k+1 is Hamiltonian, the Hamiltonicity of the Desargues graph is no surprise. (It also follows from the stronger conjecture of Lovasz that except for a few known counter-examples, all vertex-transitive graphs have Hamiltonian cycles.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Desargues graph」の詳細全文を読む スポンサード リンク
|